// 93. 复原 IP 地址
// 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），
// 整数之间用 '.' 分隔。

// 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、
// "192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
// 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，
// 这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。
// 你可以按 任何 顺序返回答案。

// 示例 1：

// 输入：s = "25525511135"
// 输出：["255.255.11.135","255.255.111.35"]
// 思路：分割字符串 且判断子串是否合法
/**
 * @param {string} s
 * @return {string[]}
 */
 var restoreIpAddresses = function(s) {
    const res=[],ans=[];
    const backtracking=function(start){
        const len=ans.length;
        // 如果长度大于4 返回越界
        if(len>4) return;
        // 长度刚好等于4且正好是最末端
        if(len===4&&start==s.length){
            res.push(ans.join("."));
            return;
        }
        // 因为不能重复分割，记录下一层递归分割的起始位置
        for(let i=start;i<s.length;i++){
            // 分割字符串
            const str=s.substr(start,i-start+1);
            // 判断规则是否符合
            if(str.length>3 || +str>255) break;// 如果大于255了不合法
            if(str.length>1 && str[0]==0) break;// 如果第一个数为0 不合法
            ans.push(str);
            backtracking(i+1);
            ans.pop();
        }
    }
    backtracking(0);
    return res;
};